package com.jiang.专题.动态规划.Q518;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/07 19:48
 */
class Solution {
    // 完全背包， 不考虑顺序（滚动数组压缩空间）
    // public int change(int amount, int[] coins) {
    //     int[] dp = new int[amount + 1];  // dp[i] 表示金额之和等于 i 的硬币组合数
    //     dp[0] = 1; // 只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合
    //     for (int coin: coins) {
    //         for (int i = coin; i <= amount; i++) {
    //             dp[i] += dp[i - coin];
    //         }
    //     }
    //     return dp[amount];
    // }

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length][amount + 1];  // dp[i][j] 表示取出值为[0, coins[i]]多个硬币，能凑出金额为j的硬币组合数
        // 第一行表示取出值为coins[0]多个硬币凑出金额为j的硬币组合数
        for(int j = coins[0]; j <= amount; j++) {
            if (j % coins[0] == 0) dp[0][j] = 1;
        }

        // 第一列表示取出值为conins[i]多个硬币凑出金额为0的硬币组合数(那么不取硬币，只有一种组合)
        for (int i = 0; i < coins.length; i++) {
            dp[i][0] = 1;
        }

        // 遍历dp数组
        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j < coins[i]) {
                    dp[i][j] = dp[i - 1][j]; // 上边
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]; // 上边 + 左边
                }
            }
        }
        return dp[coins.length - 1][amount];
    }
}
